# coding:utf-8

from typing import List


class Solution:
    # 在排序数组中查找元素的第一个和最后一个位置
    # 二分查找
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left = 0
        right = len(nums)-1
        ans = [-1,-1]
        while left <= right:
            mid = (left+right) // 2
            if nums[mid] == target:
                ans = [mid,mid]
                # 此时再左右寻找
                mid -= 1
                while mid>=0 and nums[mid] == target:
                    ans[0] -= 1
                    mid -= 1
                mid = ans[1] + 1
                while mid<len(nums) and nums[mid] == target:
                    ans[1] += 1
                    mid += 1
                break
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return ans

if __name__ == '__main__':
    solu = Solution()
    print(solu.searchRange([5,7,7,8,8,10],8))
